package main.java.Fzy.Test;

public class TestTree {

    public static void main(String[] args) {

        int[] arr = {5,6,4,8,2,11,3,10,9,0,-1};
        TestTree testTree = new TestTree();
        MyTree head = testTree.createTreeNode(arr, 1, arr.length);
        System.out.println(head.val);

        System.out.println("--------使用数组整体创建-------");
        testTree.display(head);

//        System.out.println("--------插入部分测试数据后-(插入7、1、14)---------");
//        testTree.insertTreeNode(head,7);
//        testTree.insertTreeNode(head,1);
//        testTree.insertTreeNode(head,14);
//        testTree.display(head);

//        System.out.println("--------查找数中某个元素----------");
//        MyTree myTree = testTree.find(head, 2);
//        System.out.printf("查找到数的值为:%d,右结点为:%d,左结点为:%d\n",myTree.val,myTree.right.val,myTree.left.val);

        System.out.println("----删除部分数据后-(删除-1)----------");
        MyTree myTree = testTree.deleteNode(head, -1);
        testTree.display(myTree);
        testTree.insertTreeNode(head,-1);

        System.out.println("----删除部分数据后-(删除0,保证数据完整，将上一步删除-1再次添加入BST)----------");
        MyTree myTree1 = testTree.deleteNode(head, 0);
        testTree.display(myTree1);
        testTree.insertTreeNode(head,0);

        System.out.println("----删除部分数据后-(删除5,保证数据完整，将上一步删除0再次添加入BST)----------");
        MyTree myTree2 = testTree.deleteNode(head, 5);
        testTree.display(myTree2);
        testTree.insertTreeNode(head,5);

        System.out.println("----查找最大值、最小值---------");
        System.out.printf("二叉树中最大值为:%d\n",testTree.findMax(head));
        System.out.printf("二叉树中最小值为:%d\n",testTree.findMin(head));

        System.out.println("----销毁二叉树-----------");
        testTree.destory(head);
        testTree.display(head);
    }

    /**
    * @author LazyCat
    * @date  2022/5/30
    * @param  arr:要生成树的数据  begin:开始位置  end:结束位置
    * @return 头结点
    */
    public MyTree createTreeNode(int[] arr,int begin,int end){

        if(arr == null || begin>end){
            return null;
        }
        MyTree node = new MyTree(arr[begin]);
        TestTree testTree = new TestTree();
        for(int i = begin+1;i<end;i++){
            testTree.insertTreeNode(node,arr[i]);
        }
        return node;
    }

    /**
    * @author LazyCat
    * @date  2022/6/3
    * @param val:创建树时的值
    * @return 头结点
    */
    public MyTree createTreeNode(int val){
        MyTree node = new MyTree(val);
        return node;
    }

    /**
    * @author LazyCat
    * @date  2022/5/30
    * @param  root:传入根结点 val:传入值
    * @return 是否插入成功
    */
    public boolean insertTreeNode(MyTree root,int val){

        if(root == null){
            return false;
        }
        MyTree newNode = new MyTree(val);
        MyTree cur = root;
        if(cur.val<val){
            if(cur.right == null){
                cur.right = newNode;
            }
            insertTreeNode(cur.right,val);
        }else if(cur.val>val){
            if(cur.left == null){
                cur.left = newNode;
            }
            insertTreeNode(cur.left,val);
        }
        return true;
    }
    /**
    * @author LazyCat
    * @date  2022/5/30
    * @param  root:头结点
    * @return 前序遍历
    */
    public void agoDfs(MyTree root){
        if(root == null){
            return;
        }
        System.out.print(root.val+"  ");
        agoDfs(root.left);
        agoDfs(root.right);
    }
    /**
    * @author LazyCat
    * @date  2022/5/30
    * @param root:头结点
    * @return 中序遍历
    */
    public void midDfs(MyTree root){
        if(root == null){
            return;
        }
        midDfs(root.left);
        System.out.print(root.val+"  ");
        midDfs(root.right);
    }

    /**
    * @author LazyCat
    * @date  2022/5/30
    * @param root:头结点
    * @return 后序遍历
    */
    public void afterDfs(MyTree root){
        if(root == null){
            return;
        }
        afterDfs(root.left);
        afterDfs(root.right);
        System.out.print(root.val+"  ");
    }

    /**
    * @author LazyCat
    * @date  2022/6/2
    * @param root 头结点  key:要删除的值
    * @return 返回头结点
    */
    public MyTree deleteNode(MyTree root, int key) {
        if(root == null){
            return root;
        }
        MyTree cur = root;
        if(key>cur.val){
            cur.right = deleteNode(cur.right,key);
        }
        if(key<cur.val){
            cur.left = deleteNode(cur.left,key);
        }
        if(cur.val == key) {
            if (cur.left == null) {
                cur = cur.right;
            } else if (cur.right == null) {
                cur = cur.left;
            } else {
                MyTree t = cur.left;
                while (t.right != null){
                    t = t.right;
                }
                t.right = cur.right;
                return cur.left;
            }
        }
        return cur;
    }

    /**
    * @author LazyCat
    * @date  2022/6/3
    * @param root:头结点 val:查找数值
    * @return   查找数值所在地址对象
    */
    public MyTree find(MyTree root,int val){
        if(root == null){
            return root;
        }
        if(val>root.val){
            while (val>root.val){
                root = root.right;
            }
        }
        if(val<root.val){
            while (val<root.val){
                root = root.left;
            }
        }
        if(val == root.val){
            return root;
        }
        return null;
    }
    /**
    * @author LazyCat
    * @date  2022/6/3
    * @param root:头节点
    * @return 最大值
    */
    public int findMax(MyTree root){
        if(root == null){
            return 0;
        }
        while (root.right !=null){
            root = root.right;
        }
        return root.val;
    }

    /**
    * @author LazyCat
    * @date  2022/6/3
    * @param root:头节点
    * @return 最小值
    */
    public int findMin(MyTree root){
        if(root == null){
            return 0;
        }
        while (root.left != null){
            root = root.left;
        }

        return root.val;
    }

    /**
    * @author LazyCat
    * @date  2022/6/3
    * @param root:头节点
    * @return 销毁后的头结点
    */
    public  MyTree destory(MyTree root){
        if(root == null){
            return null;
        }
        if (root.left != null) {
            root.left = destory(root.left);
        }
        if(root.right != null){
            root.right = destory(root.right);
        }
        root = null;
        return root;
    }

    /**
    * @author LazyCat
    * @date  2022/6/3
    * @param head:头结点
    * @return
    */
    public void display(MyTree head){
        TestTree testTree = new TestTree();
        System.out.print("中序遍历: ");
        testTree.midDfs(head);
        System.out.println();
        System.out.print("前序遍历: ");
        testTree.agoDfs(head);
        System.out.println();
        System.out.print("后序遍历: ");
        testTree.afterDfs(head);
        System.out.println();
    }
}
